package com.study.sort;

/**
 * - *@ClassName MergeSort
 * - *@Author LiuHuaBing
 * - *@Date 2021/12/15 13:14
 * - *@Version 1.0
 * - 归并，分治排序
 * <p>
 * 思路：L R 范围上排序 先求中点位子  先排序左侧再排右侧 再整合到一起
 * <p/>
 */
public class MergeSort {

    public static void main(String[] args) {
        int arr[] = {9, 5, 4, 8, 6, 2, -5, 93, 4};
        arr = mergeSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    private static int[] mergeSort(int[] arr, int L, int R) {
        if (L >= R) {
            return arr;
        }
        int mid = L + ((R - L) >> 1);
        mergeSort(arr, L, mid);
        mergeSort(arr, mid + 1, R);
        merge(arr, mid, L, R);
        return arr;
    }

    private static void merge(int[] arr, int mid, int L, int R) {
        int left = L;
        int right = mid + 1;
        int[] help = new int[R - L + 1];
        int helpIndex = 0;

        while (left <= mid && right <= R) {
            if (arr[left] <= arr[right]) {
                help[helpIndex] = arr[left];
                helpIndex++;
                left++;
            } else {
                help[helpIndex] = arr[right];
                helpIndex++;
                right++;
            }
        }
        while (left <= mid) {
            help[helpIndex] = arr[left];
            helpIndex++;
            left++;
        }
        while (right <= R) {
            help[helpIndex] = arr[right];
            helpIndex++;
            right++;
        }
        for (int i = 0; i <= help.length - 1; i++) {
            arr[L + i] = help[i];
        }
    }
}
